package com.lzp.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 *
 * @author lzp
 * @date 2020/03/03
 */
public class Code1 {
    /**
     * 0(n) | 0(n)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // 存放当前值和索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 满足条件的差值
            int diffVal = target - nums[i];
            if (map.containsKey(diffVal)) {
                return new int[]{map.get(diffVal), i};
            }
            // 当前值并非所需，保存值和索引
            map.put(nums[i], i);
        }
        throw new RuntimeException("无合适结果");
    }

    /**
     * 暴力求解法 0(n^2)/0(1)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == target - nums[j]) {
                    return new int[]{i, j};
                }
            }
        }
        throw new RuntimeException("无合适结果");
    }

    public static void main(String[] args) {
        Code1 code1 = new Code1();
        System.out.println(Arrays.toString(code1.twoSum(new int[]{2, 7, 11, 15}, 9)));
    }
}
